package tencent_practice;


import java.util.Random;

/**
 * 数组中的第k个最大的元素（就是排序之后的第k个元素）
 */
public class Tencent_215_findKthLargest {
    public int findKthLargest(int[] nums, int k, boolean noUse) {
        int len = nums.length;
        quickSort(nums, 0, len - 1);
        return nums[k - 1];
    }

    public static void quickSort (int[] nums, int left, int right) {
        if (left > right) {
            return;
        }
        int start = left;
        int end = right;
        int key = nums[right];

        while (start < end) {
            while (start < end && nums[start] > key) {
                start++;
            }
            while (start < end && nums[end] <= key) {
                end--;
            }
            if (start < end) {
                int remp = nums[start];
                nums[start] = nums[end];
                nums[end] = remp;
            }
        }
        nums[right] = nums[end];
        nums[end] = key;
        quickSort(nums, left, start - 1);
        quickSort(nums, start + 1, right);
    }

    /**
     * 很重要的一个方法，是这种类型的题目中
     * 可以达到时间复杂度为O(N)，空间复杂度为O(1)的
     * 必然要掌握，必然要掌握，必然要掌握
     */
//    private static Random random = new Random(System.currentTimeMillis());
//    public int findKthLargest(int[] nums, int k) {
//        int len = nums.length;
//        int left = 0;
//        int right = len - 1;
//        int target = len - k;
//        while (true) {
//            int index = partition(nums, left, right);
//            if (index < target) {
//                left = index + 1;
//            } else if (index > target) {
//                right = index - 1;
//            } else {
//                return nums[index];
//            }
//        }
//    }
//
//    private int partition(int[] nums, int left, int right) {
//        if (left < right) {
//            int randomIndex = random.nextInt(right - left) + left + 1;
//            swap(nums, left, randomIndex);
//        }
//        int pivot = nums[left];
//        int j = left;
//        for (int i = left + 1; i <= right; i++) {
//            if (nums[i] < pivot) {
//                j++;
//                swap(nums, j, i);
//            }
//        }
//        swap(nums, left, j);
//        return j;
//    }
//
//    private void swap(int[] nums, int left, int right) {
//        int temp = nums[left];
//        nums[left] = nums[right];
//        nums[right] = temp;
//    }

    private static Random random = new Random(System.currentTimeMillis());
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int target = len - k;
        int left = 0;
        int right = len - 1;
        while (true) {
            // 找到标志点的位置，用来和target做比较
            int index = partition(nums, left, right);
            if (index < target) {
                left = index + 1;
            } else if (index > target) {
                right = index - 1;
            } else {
                return nums[index];
            }
        }
    }

    /**
     * 对数组 nums 的子区间 [left...right] 中执行partition操作，返回nums[left] 排序以后应该在的位置
     * 对遍历过程中保持循环不变量的定义
     * nums[left...j] < nums[left]
     * nums[j..i] >= nums[left]
     * @param nums
     * @param left
     * @param right
     * @return
     */
    private int partition(int[] nums, int left, int right) {
        if (left < right) {
            // 找到标志点
            int randomIndex = random.nextInt(right - left) + left + 1;
            swap(nums, left, randomIndex);
        }
        int pivot = nums[left];
        int j = left;
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < pivot) {
                // j的初始值为left，先右移，再交换
                // 小于pivot的元素都被交换到前面
                j++;
                swap(nums, j, i);
            }
        }
        // 在前面的遍历中，满足了nums[left + 1...j] < pivot，并且nums[j...i] >= pivot
        // 只做了遍历并没有排序，这是需要注意点的，而且有一点需要注意的是，循环出来之后，j并不一定为right
        swap(nums, left, j);
        // 交换之后满足 nums[left + 1...j - 1] < pivot,  nums[j] = pivot, nums[j + 1...right] >= pivot
        return j;
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }


}
